//
// Created by lanlu on 2025/8/4.
//

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

class Solution {
public:
    vector<int> twoSum(vector<int> &nums, int target)
    {
        // 使用成对的容器 来存储值和初始索引
        vector<pair<int, int> > vec;
        for (int i = 0; i < nums.size(); i++)
        {
            vec.push_back(make_pair(nums[i], i));
        }
        sort(vec.begin(), vec.end());

        int left = 0, right = nums.size() - 1;
        while (left < right)
        {
            // [(-1,6), (1,5), (2,3), (7,1), (9,4), (11,2), (15,0), (15,7)]
            int sum = vec[left].first + vec[right].first;
            if (sum == target)
            {
                return {vec[left].second, vec[right].second};
            }
            if (sum < target)
            {
                left++;
            }
            else
            {
                right--;
            }
        }
        return {-1, -1};
    }
};

int main()
{
    Solution s;
    vector<int> nums = {15, 7, 11, 2, 9, 1, -1, 15};
    int target = 16;
    vector<int> res = s.twoSum(nums, target);
    cout << res[0] << "," << res[1] << endl;
}
